package done.normal_1001_1100;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 1038. Binary Search Tree to Greater Sum Tree 从二叉搜索树到更大和树
 * <p>
 * 给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
 * <p>
 * 提醒一下，二叉搜索树满足下列约束条件：
 * <p>
 * 节点的左子树仅包含键小于节点键的节点。
 * 节点的右子树仅包含键大于节点键的节点。
 * 左右子树也必须是二叉搜索树。
 * <p>
 * 示例：
 * 4                              30
 * /    \                         /     \
 * 1      6         变为          36      21
 * / \    / \       ----->       /  \    /  \
 * 0   2  5   7                  36  35  26  15
 * \      \                      \       \
 * 3      8                     33       8
 * <p>
 * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
 * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
 * 答案：
 * 反向的中序遍历，从右向左求和.preSum 保存上一次的结果
 * <p>
 * 2019-05-18 11:54
 **/
@SuppressWarnings("all")
public class BinarySearchTreeToGreaterSumTree {

    public TreeNode bstToGst(TreeNode root) {
        // 190518 first
        return null;
    }

    @Test
    public void test() {
        info(bstToGst(new TreeNode(4,
                new TreeNode(1,
                        0, new TreeNode(2,
                        null, 3)), new TreeNode(6,
                5, new TreeNode(7,
                null, 8)))));
    }
}







































/*
int res;
public TreeNode bstToGst(TreeNode root) {
    if (root==null)
        return null;

    bstToGst(root.right);

    root.val += res;
    res = root.val;

    bstToGst(root.left);
    return root;
}
*/